package com.cet.algorithm.二叉树.二叉搜索树的最近公共祖先;

/**
 * @program: cet-practice
 * @description: BST最近公共祖先
 * @author: 陈恩涛
 * @create: 2023-04-06 19:04
 **/
public class LC235 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10, new TreeNode(5, new TreeNode(3, new TreeNode(1), null), new TreeNode(8, new TreeNode(6), new TreeNode(9))), new TreeNode(11, null, new TreeNode(12)));
        System.out.println(lowestCommonAncestor(root, new TreeNode(1), new TreeNode(9)).val);
    }

    /**
     * 因为BST中序遍历为有序序列，第一次遇到node.val > p.val && node.val < q(反之亦然)
     * 即为最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null) {
            return root;
        }

        // 目标在节点在左子树
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }

        // 目标节点在由子树
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }

    /**
     * BST最小公共祖先，迭代法
     * @param root
     * @param p
     * @param q
     * @return
     */
    static TreeNode lowestCommonAncestorIterate(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (root.val > p.val && root.val > q.val) {
                root = root.left;
            } else if (root.val < p.val && root.val < q.val) {
                root = root.right;
            } else {
                break;
            }
        }
        return root;
    }
}
